package com.LeeCode;

/**
 * K 连续位的最小翻转次数
 */

public class Code995 {
    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 1, 0, 1, 1, 0};
        int k = 3;
        System.out.println(new Code995().minKBitFlips(nums, k));
    }

    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int[] diff = new int[n + 1];  // 差分数组
        int flipped = 0;              // 是否翻转
        int result = 0;               // 翻转次数

        for (int i = 0; i < n; i++) {
            flipped ^= diff[i];       // 更新当前翻转状态

            // 计算当前位置的实际值
            int actualValue = nums[i] ^ (flipped);

            // 如果实际值是 0，需要翻转
            if (actualValue == 0) {
                // 检查是否还有足够的空间进行 k 位翻转
                if (i + k > n) {
                    return -1;  // 不可能完成
                }

                // 进行翻转操作
                result++;
                flipped ^= 1;           // 更新翻转状态
                diff[i] ^= 1;           // 在位置 i 开始翻转
                diff[i + k] ^= 1;       // 在位置 i+k 结束翻转
            }
        }

        return result;
    }
}
